package cn.yuemouren.stack.leetcode;

import java.util.Stack;

/**
 * @Author: Timi
 * @Description: 20.有效的括号
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 *
 * 解题思路：
 *      1、先将左侧括号入栈，随后匹配 ，匹配不上返回false，最终以栈为空表示匹配完成
 *      2. 判断左侧括号，将右侧扩号入栈，最后比对栈中的右括号与字符串中右括号是否匹配
 * @Date: 2020/5/9 14:11
 */
public class ValidParenthesis_20 {

    public static void main(String[] args) {
        String s = "\"\"";
        boolean valid = isValid(s);
        System.out.println(valid);
    }

    /**
     * 运行时间一毫秒
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || c != stack.pop()) return false;
        }
        return stack.isEmpty();
    }
    /**
     * 2ms
     */
   /* public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);
            } else{
                if(stack.isEmpty()){
                    return false;
                }
                Character top = stack.pop();
                if(c == ')' && top != '('){
                    return false;
                }
                if(c == ']' && top != '['){
                    return false;
                }
                if(c == '}' && top != '{'){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }*/
}
